A miss rate curve (MRC) describes the impact of memory allocation on the miss rate of a workload. A “miss” in this context refers to an access to a memory page not currently resident in memory, which incurs a page fault and requires the memory page to be retrieved from a slower tier of storage, such as disks, solid state drives, or a compression cache. Given the MRC data, an administrator or a memory allocation unit under control of a program may perform qualitative cost-benefit tradeoffs when allocating memory resources among multiple applications. Therefore, in situations where there is over-commitment of memory, such as virtual machines (VMs) running on a common host machine, the MRC data for the VMs can inform the administrator or the memory allocation unit how to allocate memory resources across the VMs in an optimal manner.
Various techniques are known in the art for constructing MRCs. Most existing MRC construction techniques rely on the Mattson Stack Algorithm, which maintains a least-recently used (LRU) ordered stack of memory references. In these techniques, all memory pages are traced for access, and page numbers corresponding to the memory pages are pushed onto the stack as they are referenced. When a page is accessed again, its stack distance from the top-of-stack position is noted, and its page number is moved to the top of the stack. The result is a histogram of accesses at various stack distances. This data can be used to compute the miss rate that would be observed at different memory allocations, and construct the MRC based on the relationship between the miss rates and the memory allocations.
The tracing of memory pages, however, incurs a fairly expensive page fault when any one of the memory pages is accessed. Handling these page faults typically consumes thousands of processor cycles. In addition, the memory space required to maintain an LRU ordered stack for all of the memory pages can be quite large. Consequently, although MRCs have been used in informing memory management decisions, the overheads reported for MRC construction techniques, in terms of memory space and processor cycles, are too high for online or production use.